//
// Created by Lenovo on 2021/5/27.
//

#ifndef TSP_ACO_H
#define TSP_ACO_H
#include <cstring>
#include <iostream>
#include <fstream>
#include <iomanip>
#include <cmath>
#include <vector>
#include <algorithm>
#include <map>
#define debug(x) cout<<#x<<" :"<<x<<endl
using namespace std;
const  int MAX_city =  1e3+1;
const int star = 14;
const  int MAX_ant = 3e3+1;
const  int NC = 100;
const double C = 100;
const double Alpha = 1;
const double Beta = 5;
const double Rho = 0.9;
const double Q = 1e6+1;
double D[MAX_city][MAX_city];//邻接矩阵
double Csite[MAX_city][2];//城市座标
double Eta[MAX_city][MAX_city];//由城市i到j的期望程度
double DeltaTau[MAX_city][MAX_city];
double Tau[MAX_city][MAX_city];
double best_len[NC+1];
double ave_len[NC];
vector<int>best_route[NC+1];
vector<int>tabu[MAX_ant];
map<int,int>visited[MAX_city];

class Ant
{
public:
    void tabu_clear(){
        for(int i = 0;i<MAX_ant;i++){
            tabu[i].clear();
            visited[i].clear();
            tabu[i].push_back(star);
            visited[i][star] = 1;
        }
    }
    void init(){
        for(int i = 0;i<MAX_city;i++){
            for(int j = 0;j<MAX_city;j++){
                if(i!=j)  Eta[i][j] = (C*C)/D[i][j];
                else Eta[i][j] = 0;
                Tau[i][j] = C;
                DeltaTau[i][j] = 0;
            }
        }
    }
    void updata_D(){
        for(int i = 0;i<citynum;i++){
            for(int j = i+1;j<citynum;j++){
                double  x = Csite[i][0]-Csite[j][0];
                double  y = Csite[i][1]-Csite[j][1];
                double ans = fabs(x*x+y*y);
                D[i][j] = D[j][i] = sqrt(ans);
            }
        }
    }
    void updata_Csite(string fname="")//更新城市座标
    {
        int cnt = 0;
        if(fname == "") clear_Csite();
        else
        {
            ifstream infile;
            infile.open(fname);
            if(!infile.is_open()) {
                puts("error");
                return;
            }
            string buf;
            int loc;
            double x,y;
            for(int i = 0;i<6;i++) getline(infile,buf);
            while(infile>>loc>>x>>y){
                Csite[loc-1][0] = x;
                Csite[loc-1][1] = y;
                cnt++;
            }
            citynum = cnt;
            antnum = 100;
        }
        updata_D();
        init();
        solve();
    }
    void clear_Csite(){
        for(int i = 0;i<MAX_city;i++) Csite[i][0] = Csite[i][1] = 0;
    }
    void solve(){
        while(nc<NC)
        {
            debug(nc);
            double minn = 1e17;
            tabu_clear();
            for(int index = 1;index<citynum;index++)
            {
                for(int k = 0;k<antnum;k++)
                {
                    double Psum = 0;
                    double pick;
                    vector<int>to_visit;
                    vector<double>p;
                    for(int i = 0;i<citynum;i++)
                    {

                        if(!visited[k][i])
                        {
                                to_visit.push_back(i);
                                double tmp_p = pow(Tau[tabu[k].back()][i],Alpha)*pow(Eta[tabu[k].back()][i],Beta);
                                Psum += tmp_p;
                                p.push_back(tmp_p);
                        }
                    }
                    for(int i = 0;i<p.size();i++) p[i] = p[i]/Psum;
                    pick = (double)rand()/RAND_MAX;
                    for(int i = 0;i<p.size();i++){
                        pick -= p[i];
                        if(pick<=0){
                            tabu[k].push_back(to_visit[i]);
                            visited[k][to_visit[i]] = 1;
                            break;
                        }
                    }
                }
            }
            for(int i = 0;i<antnum;i++)
            {
                tabu[i].push_back(star);
            }
            vector<double>nlen;//本轮每只蚂蚁走过的路程长度
            double lensum = 0;
            for(int i = 0;i<antnum;i++){
                double len = 0;
                int u = tabu[i][0];
                for(int j = 1;j<tabu[i].size();j++)
                {
                    int v = tabu[i][j];
                    len += D[u][v];
                    u = v;
                }
                lensum += len;
                nlen.push_back(len);
                if(len<minn) {
                    best_len[nc] = len;
                    minn = len;
                    best_route[nc] = tabu[i];
                }
            }
            ave_len[nc] = lensum/antnum;
            for(int i = 0;i<antnum;i++){
                int u = tabu[i][0];
                for(int j = 1;j<tabu[i].size();j++)
                {
                    int v = tabu[i][j];
                    DeltaTau[u][v] += (Q/nlen[i]);
                    u = v;
                }
            }
            for(int i = 0;i<citynum;i++)
            {
                for(int j = 0;j<citynum;j++)
                {
                    Tau[i][j] = Rho*Tau[i][j] + DeltaTau[i][j];
                    DeltaTau[i][j] = 0;
                }
            }
            nc++;
        }
    }
    void ans(string fname){
        fstream  ofs;
        ofs.open(fname,ios::out);
        int flag = 0;
        ofs<<"NC"<<" "<<"ave_len"<<" "<<"best_len"<<endl;
        for(int i = 0;i<NC;i++){
            if(best_len[i]<best_len[flag]) flag = i;
            ofs<<i<<" "<<ave_len[i]<<" "<<best_len[i]<<endl;
        }
        ofs<<"all ave_len and best_len:"<<endl;
        ofs<<ave_len[flag]<<" "<<best_len[flag]<<endl;
        ofs<<"pos  loc_x loc_y"<<endl;
        for(int i = 0;i<best_route[flag].size();i++) ofs<<best_route[flag][i]<<" "<<Csite[best_route[flag][i]][0]<<" "<<Csite[best_route[flag][i]][1]<<endl;
        ofs.close();
    }
private:
    int citynum;
    int antnum;
    int nc = 0;
};
#endif //TSP_ACO_H
